/*
    XTU OJ: 1396
    by: fifth_light
*/

#include <stdio.h>

char table[1000050] = {0};
int results[1000050] = {0};
int ranges[1000050] = {0};

void prepare_table() {
    table[0] = 1;
    table[1] = 1;
    for (int i = 2; i < 1050; i == 2 ? (i = 3) : (i += 2)) {
        for (int n = i; n < 1000050; n += i) {
            if (i != n) table[n] = 1;
        }
    }
    
    for (int i = 2; i < 1000050; i++) {
        if (table[i] == 0) {
            for (int j = i; j < 1000050; j += i) {
                int n = 0;
                for (int k = j; k % i == 0; k /= i, n++);
                results[j] += n;
            }
        }
    }
    
    int res = 0;
    for (int i = 0; i < 1000050; i++) {
        ranges[i] = (res += results[i]);
    }
}

int prime_count(int start, int end) {
    if (start > end) {
        int tmp = end;
        end = start;
        start = tmp;
    }
    return ranges[end] - ranges[start - 1];
}

int main(void) {
    prepare_table();
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", prime_count(a, b));
    }
    return 0;
}
